# LeetCode 852、山脉数组的顶峰索引
# 一、题目描述
符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3- 存在
i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] <... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 1：
输入：arr = [0,1,0] 输出：1
示例 2：
输入：arr = [0,2,1,0] 输出：1
示例 3：
输入：arr = [0,10,5,2] 输出：1
示例 4：
输入：arr = [3,4,5,1] 输出：2
提示
3 <= arr.length <= 1040 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组
**进阶：**很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 山脉数组的峰顶索引（ LeetCode 852 ）:https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution {
public int peakIndexInMountainArray(int[] arr) {
// 题目告诉我们 3 <= arr.length <= 10^4
// 也就是说 arr 的最左侧和最右侧肯定不是山峰
// 所以如果存在山脉，数组中最左侧的元素肯定不是山脉的山峰位置，因为它的左侧没有元素了
// 因此，搜索区间需要从索引为 1 的位置开始
int left = 1;
// 同样的，如果存在山脉，数组中最右侧的元素肯定不是山脉的山峰位置，因为它的右侧没有元素了
// 因此，搜索区间需要从索引为 nums.length - 2 的位置结束
int right = arr.length - 2;
// 在 while 循环里面，left 不断的 ++，而 right 不断的 --
// 当 left 和 right 相等， [ left , right ] 这个区间存在一个元素的时候
// 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
// 所以，当 left == right 时，跳出循环
// 此时，while 循环的判断不可以可以使用等号
while(left < right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 由于题目中提示【题目数据保证 arr 是一个山脉数组】
// 所以对于 arr 中任意位置的元素，比如 mid 所在的位置，只有以下三种情况
// 1、mid 处于山峰位置，也就是它的值大于左侧，也大于右侧
// arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]
// 此时，找到了结果
if( arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1] ){
// 返回结果
return mid;
}
// 2、mid 处于上升状态，也就是它的值大于左侧，同时小于右侧
// arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]
// 那么，我们需要在右侧区间去寻找出下降的那段
if( arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]){
// 缩小区间，从 [ mid + 1 , right ] 里面去找
left = mid + 1;
}
// 3、mid 处于下降状态，也就是它的值小于左侧，同时小于右侧
// arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]
// 那么，我们需要在左侧区间去寻找出上升的那段
if( arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1] ){
// 缩小区间，从 [ left , mid - 1 ] 里面去找
right = mid - 1;
}
}
// 跳出循环，此时 left == right，区间为 [ left，right ]，只有一个元素
// 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
// 返回这个下标即可
return left;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 山脉数组的峰顶索引（ LeetCode 852 ）:https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
// 题目告诉我们 3 <= arr.length <= 10^4
// 也就是说 arr 的最左侧和最右侧肯定不是山峰
// 所以如果存在山脉，数组中最左侧的元素肯定不是山脉的山峰位置，因为它的左侧没有元素了
// 因此，搜索区间需要从索引为 1 的位置开始
int left = 1;
// 同样的，如果存在山脉，数组中最右侧的元素肯定不是山脉的山峰位置，因为它的右侧没有元素了
// 因此，搜索区间需要从索引为 nums.length - 2 的位置结束
int right = arr.size() - 2;
// 在 while 循环里面，left 不断的 ++，而 right 不断的 --
// 当 left 和 right 相等， [ left , right ] 这个区间存在一个元素的时候
// 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
// 所以，当 left == right 时，跳出循环
// 此时，while 循环的判断不可以可以使用等号
while(left < right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 由于题目中提示【题目数据保证 arr 是一个山脉数组】
// 所以对于 arr 中任意位置的元素，比如 mid 所在的位置，只有以下三种情况
// 1、mid 处于山峰位置，也就是它的值大于左侧，也大于右侧
// arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]
// 此时，找到了结果
if( arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1] ){
// 返回结果
return mid;
}
// 2、mid 处于上升状态，也就是它的值大于左侧，同时小于右侧
// arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]
// 那么，我们需要在右侧区间去寻找出下降的那段
if( arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]){
// 缩小区间，从 [ mid + 1 , right ] 里面去找
left = mid + 1;
}
// 3、mid 处于下降状态，也就是它的值小于左侧，同时小于右侧
// arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]
// 那么，我们需要在左侧区间去寻找出上升的那段
if( arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1] ){
// 缩小区间，从 [ left , mid - 1 ] 里面去找
right = mid - 1;
}
}
// 跳出循环，此时 left == right，区间为 [ left，right ]，只有一个元素
// 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
// 返回这个下标即可
return left;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 山脉数组的峰顶索引（ LeetCode 852 ）:https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
# 题目告诉我们 3 <= arr.length <= 10^4
# 也就是说 arr 的最左侧和最右侧肯定不是山峰
# 所以如果存在山脉，数组中最左侧的元素肯定不是山脉的山峰位置，因为它的左侧没有元素了
# 因此，搜索区间需要从索引为 1 的位置开始
left = 1
# 同样的，如果存在山脉，数组中最右侧的元素肯定不是山脉的山峰位置，因为它的右侧没有元素了
# 因此，搜索区间需要从索引为 nums.length - 2 的位置结束
right = len(arr) - 2
# 在 while 循环里面，left 不断的 ++，而 right 不断的 --
# 当 left 和 right 相等， [ left , right ] 这个区间存在一个元素的时候
# 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
# 所以，当 left == right 时，跳出循环
# 此时，while 循环的判断不可以可以使用等号
while left < right :
# left + (right - left) / 2 和 (left + right) / 2 的结果相同
# 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
# 比如数据 int 的最大值为 2,147,483,647
# 此时，left 为 2,147,483,640
# 此时，right 为 2,147,483,646
# 两者直接相加超过了 2,147,483,647，产生了溢出
mid = left + (right - left) // 2
# 由于题目中提示【题目数据保证 arr 是一个山脉数组】
# 所以对于 arr 中任意位置的元素，比如 mid 所在的位置，只有以下三种情况
# 1、mid 处于山峰位置，也就是它的值大于左侧，也大于右侧
# arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1]
# 此时，找到了结果
if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1] :
# 返回结果
return mid
# 2、mid 处于上升状态，也就是它的值大于左侧，同时小于右侧
# arr[mid] > arr[mid - 1] and arr[mid] < arr[mid + 1]
# 那么，我们需要在右侧区间去寻找出下降的那段
if arr[mid] > arr[mid - 1] and arr[mid] < arr[mid + 1] :
# 缩小区间，从 [ mid + 1 , right ] 里面去找
left = mid + 1
# 3、mid 处于下降状态，也就是它的值小于左侧，同时小于右侧
# arr[mid] < arr[mid - 1] and arr[mid] > arr[mid + 1]
# 那么，我们需要在左侧区间去寻找出上升的那段
if arr[mid] < arr[mid - 1] and arr[mid] > arr[mid + 1] :
# 缩小区间，从 [ left , mid - 1 ] 里面去找
right = mid - 1
# 跳出循环，此时 left == right，区间为 [ left，right ]，只有一个元素
# 这也意味着这个区间里面的元素找不到其它元素和它进行比较，它已经傲视群峰，就是山脉，得到结果
# 返回这个下标即可
return left